package sort;

/**
 * @author Europa
 * @create 2020-05-15 19:11
 */
public class Quick extends Sort {

    /**
     * 快速排序<br/>
     * 可视化 https://www.bilibili.com/video/BV1ax411U7zk/
     *
     * @param array int数组
     */
    @Override
    public void sort(int[] array) {
        sort(array, 0, array.length - 1);
    }

    /**
     * 快速排序
     *
     * @param array int数组
     * @param left  左边界
     * @param right 右边界
     */
    private void sort(int[] array, int left, int right) {
        if (left >= right) {
            return;
        }
        int index = partition(array, left, right);
        sort(array, left, index - 1);
        sort(array, index + 1, right);
    }

    /**
     * 基准
     *
     * @param array int数组
     * @param left  左边界
     * @param right 右边界
     * @return 新基准
     */
    private int partition(int[] array, int left, int right) {
        int l = left;
        int r = right + 1;
        int base = array[left];
        while (true) {
            //当array[l] < base 时,就++l,直到l == 右边界
            while (less(array[++l], base)) {
                if (l == right) {
                    break;
                }
            }
            //当base < array[r]时,就--r,直到r == 左边界
            while (less(base, array[--r])) {
                if (r == left) {
                    break;
                }
            }
            //当左边界 >= 右边界时,循环停止
            if (l >= r) {
                break;
            }
            //这时 l < r,将小于基准的放左边,大于的放右边
            exchange(array, l, r);
        }
        //这时 l >= r,到这里数组已经无法分割了
        exchange(array, left, r);
        return r;
    }
}
